package PersonStu.sanqi;

/**
 * @Author: Dijah
 * @Date: 2022/12/8 14:22
 * @Desc: 完全二叉树的节点个数
 * 描述：
 * 1、给定一个完全二叉树的头结点 head，返回这棵树的节点的个数
 * 要求：
 * 如果完全二叉树的节点个数为N，要求实现时间复杂度低于O(N)的解法
 * 思路：
 * 1、如果head==null，说明是空树，直接返回为0
 * 2、如果不是空树，求树的高度，方式：找到树的最左的节点在哪一层，层数几位h
 * 3、使用递归过程记为bs（node,l,h）,node表示当前节点，l表示node所在的层数，h表示整棵树的层数
 * 全部过程
 * 每一层只会选择一个节点node 进行bs的递归过程，所以调用bs函数的次数为O（h）。
 * 每次调用bs函数时，都会查看node右子树的最左节点，所以只会遍历O（h）个节点，整个过程的时间复杂度为O(h^2)
 */
public class code_10_CompleteTreeNodeNumber {

    public static class Node{
        public int value;
        public Node left;
        public Node right;

        public Node(int data){this.value = data;}
    }

    public static int nodeNum(Node head){
        if(head == null){
            return 0;
        }
        return bs(head,1,mostLeftLevel(head,1));
    }

    /**
     *
     * @param head 头结点
     * @param level node在第level层
     * @param h 树的深度，是不变的
     * @return
     */
    private static int bs(Node head, int level, int h) {
        if(level == h){
            return 1;
        }
        if(mostLeftLevel(head.right,level + 1) == h){
            return (1 << (h - level)) + bs(head.right,level + 1,h);
        }else {
            return (1 << (h - level - 1)) + bs(head.left,level + 1,h);
        }
    }

    /**
     *
     * @param head 头
     * @param level 层数
     * @return
     * 如果node在第level层
     * 以node为头的子树，最大深度是多少
     */
    private static int mostLeftLevel(Node head, int level) {
        while (head != null){
            level++;
            head = head.left;
        }
        return level - 1;
    }

    public static void main(String[] args) {
        Node node1 = new Node(1);
        Node node2 = new Node(2);
        Node node3 = new Node(3);
        Node node4 = new Node(4);
        Node node5 = new Node(5);
        Node node6 = new Node(6);
        Node node7 = new Node(7);
        Node node8 = new Node(8);
        Node node9 = new Node(9);
        node1.left = node2;
        node1.right = node3;
        node2.left = node4;
        node2.right = node5;
        node3.left = node6;
        node3.right = node7;
        node4.left = node8;
        node4.right = node9;
        System.out.println(nodeNum(node1));
    }
}
